package leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 面试题17.14.最小K个数
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可.
 * 输入：arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出：[1,2,3,4]
 */
public class Interview_1714 {
    //时间复杂度O(nlogk)
    public int[] smallestK(int[] arr, int k) {
        if(arr.length == 0 || k == 0) {
            return new int[0];
        }
        //找最小的数用最大堆，改造JDK默认的最小堆,使队首元素是最大值
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //扫描原数组，让优先级队列中只存储k个元素
        for(int i : arr) {
            if(queue.size() < k){
                //直接入队
                queue.offer(i);
            }else if(i < queue.peek()){
                //当前元素 < 队首元素时,先让弹出队首元素
                queue.poll();
                //再让该元素入队
                queue.offer(i);
            }
        }
        //此时队列中存储了k个最小的元素
        int[] mins = new int[k];
        for(int i = 0; i < k; i++){
            mins[i] = queue.poll();
        }
        return mins;
    }
}
